#include "hashtable.h"//可能要改回去
#include<string.h>
#include<string>
#include <algorithm>
#define MAGIC 9997
#define MULT 31
/*
你需要实现一个哈希函数，以及一个哈希表的类。这个表可以用线性探测法规避冲突，
也可以使用不改变函数签名的其它方法规避冲突，只要遵守题目中的约定。
这里给你提供一些哈希函数的设计思路 Wikipedia: Hash Function。
每个Node对象中含有一个pair，
其中第一个元素是一个单词的字符串，第二个元素是一个整数型，表示词频。
*/

bool Node::operator!=(const char *str) {
    //TODO
    //重载不等号操作符；如果str与Node里的字符串不一样，则返回true。
    if(str==NULL)return false;
    pair<string,int>tp=(*this->get_pair());
    string this_string=tp.first;
    if(strcmp(str,this_string.c_str())==0)
    {
        return false;
    }
    return true;
}

bool Node::operator!=(const string &str) {
    //TODO
    //重载不等号操作符；如果str与Node里的字符串不一样，则返回true。
    //if(str==NULL)return false;
    pair<string,int>tp=(*this->get_pair());
    string this_string=tp.first;
    if(str==this_string)
    {
        return false;
    }
    return true;
}

bool Node::operator==(const char *str) {
    //TODO
    //重载等号操作符；如果str与Node里的字符串一样，则返回true。
    if(str==NULL)return false;
    pair<string,int>tp=*this->get_pair();
    string this_string=tp.first;
    if(strcmp(str,this_string.c_str())==0)
    {
        return true;
    }
    return false;
}

bool Node::operator==(const string &str) {
    //TODO
    //重载等号操作符；如果str与Node里的字符串一样，则返回true。
    pair<string,int>tp=(*this->get_pair());
    string this_string=tp.first;
    if(str==this_string)
    {
        return true;
    }
    return false;
}

bool Node::operator!=(Node &n) {
    //TODO
    //重载不等号操作符；如果n与Node里的字符串不一样，则返回true。
    string str1=n.get_pair()->first;
    string str2=this->get_pair()->first;
    if(str1==str2)return false;
    return true;
}

bool Node::operator==(Node &n) {
    //TODO
    //重载等号操作符；如果n与Node里的字符串一样，则返回true。
    string str1=n.get_pair()->first;
    string str2=this->get_pair()->first;
    if(str1==str2)return true;
    return false;
}

char Node::operator[](const int index) {
    //TODO
    //重载方括号[]操作符，返回字符串中下标对应的字符char。
    string str=this->get_pair()->first;
    if(index<0||index>=str.length())return '\0';
    return str[index];
}

int Node::length() { //return length of the string
    //TODO
    //返回字符串的长度。
    string str=this->get_pair()->first;
    return str.length();
}

int &Node::second() {
    //TODO
    //返回pair中第二个元素（就是那个整数型变量）的引用；
    int a=this->get_pair()->second;
    int &b=a;
    return b;
}

const pair<string, int>* Node::get_pair() const {
    //TODO
    //返回一个指向pair的指针；
    //if(this->get_pair()==NULL)return NULL;
    return &(this->p);
}

Node::~Node() {
    //TODO
    //Node的析构函数；你需要清理 Node 的所有内存。

}

HashTable::HashTable() {
    //TODO
    //HashTable的构造函数；建造构造函数，初始化相关变量。
    elem=new Node[MAGIC];
    size=MAGIC;
}

HashTable::~HashTable() {
    //TODO
    //HasnTable的析构函数；你需要清理 HashTable 的所有内存。
    delete []elem;
    elem=NULL;
}

int HashTable::hash(Node &index) {
    //TODO
    //很明显这是一个哈希函数。你需要将一个 Node 对象转为一个整数。
    //这里自己创造一种映射方法
    string str=index.get_pair()->first;
    int h=1;
    for(int i=0;i<str.length();i++)
    {
        h=h*str[i];
    }
    return (h%MAGIC>=0)?h%MAGIC:(h%MAGIC+MAGIC);
}

bool HashTable::search(Node &index, int &pos, int &times) {
    //TODO
    //HashTable的查找函数，如果函数查找index成功，则返回true，否则返回false。
    //pos记录哈希表可插入index的位置，times记录发生冲突的次数。
    int h=hash(index);
    string this_first=elem[h].get_pair()->first;
    if(this_first=="#")//如果index该在的位置为空，说明hash里无index
    {
        pos=h;
        times=0;
        return false;
    }
    else//对应位置有元素
    {
        if(index==elem[h])//这个元素就是index
        {
            pos=h;//无需插入返回-1
            times=0;
            return true;//查找成功
        }
        else//这个元素不是index，index可能在后面
        {
            //find
            //从h开始遍历
            times=1;
            for(int i=(h+1)%MAGIC;i!=h;i++,i=i%MAGIC)
            {
                if(elem[i].first()=="#")//在h后发现空位，此时仍未找到，则说明不存在
                {
                    pos=i;
                    return false;//没有找到，但在pos可以插入
                }
                if(index==elem[i])//若找到了返回
                {
                    pos=i;
                    return true;
                }
                times++;
            }
            pos=-1;
            return false;
        }
    }
    
    return false;
}

int HashTable::insert(Node &index) {
    //TODO
    //插入一个Node类；如果请求目标存在表中则返回 2。
    //其它情况请返回 1 或 0。（你自行决定，方便你之后 Debug）
    int pos,times;
    string s=index.get_pair()->first;
    if(s=="")return 0;
    if(!words_check(index))return 0;//不是字母返回0
    transform(s.begin(),s.end(),s.begin(),::tolower);
    index.set_first(s);
    if(search(index,pos,times))//目标存在返回2
    {
        elem[pos].set_second(elem[pos].second()+1);
        return 2;
    }
    else
    {
        if(pos=-1)return 0;//哈希表满了
        elem[pos].set_first(index.first());
        elem[pos].set_second(index.second());
    }
    return 1;//正常插入返回1
}

int HashTable::insert(const char * str) {
    //TODO
    //插入一个 C 式的字符串（即一个char的数组）；如果请求目标存在表中则返回 2。其它情况请返回 1 或 0。（你自行决定，方便之后 Debug）
    //很明显作为一个词频统计项目，插入元素后你需要更新这个字符串对应的词频。
    int pos,times;
    string s=str;
    if(s=="")return 0;//空字符不接受
    transform(s.begin(),s.end(),s.begin(),::tolower);
    Node new_node=Node(s);
    if(!words_check(new_node))return 1;
    
    if(search(new_node,pos,times))
    {
        elem[pos].set_second(elem[pos].second()+1);
        return 2;
    }
    else
    {
        if(pos==-1)return 0;//哈希表满了
        elem[pos].set_first((new_node).first());
        elem[pos].set_second((new_node).second());
    }
    return 1;
}

int Node::set_second(int s)
{
    this->p.second=s;
}

int Node::set_first(string s)
{
    this->p.first=s;
}

const string Node::first()
{
    return this->p.first;
}

bool HashTable::words_check(Node& index)
{
    string str=index.get_pair()->first;
    for(int i=0;i<str.length();i++)
    {
        if(!isalpha(str[i]))return false;
    }
    return true;
}

/*
 ==========================================================================
 =================Please Do Not Modify Functions Below=====================
 ========================请不要修改下列函数实现================================
 ==========================================================================
 */

Node::Node() {
    p = make_pair(string("#"), 1);
}

Node::Node(const char *str) {
    p = make_pair(string(str), 1);
}

Node::Node(const string &str) {
    p = make_pair(str, 1);
}

int HashTable::get_size() const {
    return size;
}

const pair<string, int>* HashTable::get_pair(int index) {
    if (index < size && index >= 0) {
        return (elem[index].get_pair());
    }
    return NULL;
}

const pair<string, int>* HashTable::get_pair(int index) const {
    if (index < size && index >= 0) {
        return (elem[index].get_pair());
    }
    return NULL;
}
